1. Field of the Invention
The present invention relates to an error correcting apparatus, and more particularly, to a Galois field processor having a dual parallel data path for a Bose Chaudhuri Hocquenghem/Reed-Solomon (BCH/RS) decoder capable of improving the performance of a decoder using a dual data path in the BCH/RS decoder.
2. Description of the Related Art
With the development of digital technology, techniques for recovering from errors generated in channels or media have been developed. Various error correction techniques have been reported and developed. Among the techniques, a Bose Chaudhuri Hocquenghem/Reed-Solomon (BCH/RS) code, which is a type of linear block code, is most widely used due to its excellent error correction capability and efficient encoding and decoding procedures. The decoding procedure of the BCH/RS code is more complicated than its encoding procedure. As the number of systems which require high speed digital data processing increases, decoding hardware increasingly requires architecture in which high speed digital processing can be performed.
However, previously known decoding hardware architectures do not readily process data at speeds as high as required. The main functions of a BCH/RS decoder includes 1) calculating from a transmitted code a syndrome having information on the presence of errors, 2) calculating the coefficients of an error location polynomial from the calculated syndrome, 3) calculating the roots of the error location polynomial, 4) searching for an error value, and 5) recovering the error using the error location polynomial roots and the error value.
In this approach, calculating the roots of the error location polynomial requires the most complicated process and hardware. Therefore, this is typically regarded as the most important step in determining the high speed operation and the error correction ability of the BCH/RS decoder. Various approaches to performing this step have been reported. The Euclidian algorithm and the feedback shift register (FSR) synthesis algorithm suggested by Massey-Berlekamp are commonly used in no less than three symbols of multiple error correction. However, since a plurality of multipliers and long latency are required when the Euclidian algorithm is realized as hardware, the Massey-Berlekamp algorithm is commonly used when a high speed correction is required.
The number of multipliers and inverse circuits and the latency during execution processes also vary in the Massey-Berlekamp algorithm according to how the algorithm is realized. This significantly affects the size and the performance of the hardware.
To solve the above problem, it is an object of the present invention to provide a Galois field processor having a dual parallel data path for a Bose Chaudhuri Hocquenghem/Reed-Solomon (BCH/RS) decoder, which has a small area and operates at a high speed and where the latency during execution processes can be minimized.
Accordingly, to achieve the above object, there is provided a Galois field processor having a dual parallel data path for a Bose Chaudhuri Hocquenghem/Reed-Solomon (BCH/RS) decoder. The processor of the invention includes a syndrome register block having an even-degree syndrome register block for storing even-degree syndrome values from among the syndrome values transmitted by a syndrome generating block and an odd-degree syndrome register block for storing odd-degree syndrome values from among the syndrome values transmitted by the syndrome generating block. A correction polynomial register block includes an even-degree correction polynomial coefficient register block for receiving an even-degree coefficient output and storing even-degree coefficients of a correction polynomial, and an odd-degree correction polynomial coefficient register block for receiving an odd-degree coefficient output and storing odd-degree coefficients of the correction polynomial. A connection polynomial register block includes: (i) an even-degree modified connection polynomial coefficient register block for receiving the even-degree coefficient output and storing the even-degree coefficients of a modified connection polynomial, (ii) an odd-degree modified connection polynomial coefficient register block for receiving the odd-degree coefficient output and storing the odd-degree coefficients of the modified connection polynomial, (iii) an even-degree connection polynomial coefficient register block for receiving the even-degree coefficient output and the output of the even-degree modified connection polynomial coefficient register block and outputting the even-degree coefficients of a connection polynomial, and (iv) an odd-degree connection polynomial coefficient register block for receiving the odd-degree coefficient output and the output of the odd-degree modified connection polynomial coefficient register block and outputting the odd-degree coefficients of the connection polynomial. A discrepancy register block receives delta output and storing a discrepancy value for updating the connection polynomial so as to continuously generate syndromes equal to previously known syndromes. A dual mode Galois field data path (DMGFDP) includes a first data path for (i) receiving the respective outputs of the syndrome register block, the correction polynomial register block, the connection polynomial register block and the discrepancy register block, (ii) performing first predetermined operations related to the even-degree coefficients of the correction and connection polynomials, and (iii) outputting the even-degree coefficient result of the first predetermined operations. The DMGFDP also includes a second data path for (i) performing second predetermined operations related to the odd-degree coefficients of the correction and connection polynomials and (ii) outputting the odd-degree coefficient result of the second predetermined operations. The DMGFDP also includes a delta output unit for performing third predetermined operations related to the even-degree and odd-degree coefficients of the connection polynomial and outputting the delta output result of the third predetermined operations. An output unit synthesizes the output of the even-degree connection polynomial coefficient register block with the output of the odd -degree connection polynomial coefficient register block and outputs the synthesis results as the coefficients of an error location polynomial, according to a control signal.
In one embodiment, the first data path includes a first register fetch unit which includes: (i) a first input register for selecting, storing and outputting one of the output of the discrepancy register block, the output of the even-degree connection polynomial coefficient register block, and the data of a first bypass bus, (ii) a second input register for selecting, storing and outputting one of the output of the discrepancy register block and the output of the even-degree syndrome register block, and (iii) a third input register for selecting, storing and outputting one of the output of the even-degree correction polynomial coefficient register, the output of the even-degree connection polynomial coefficient register block, and the output of the odd-degree connection polynomial coefficient register block. A first execute unit includes a first multiplier for multiplying the output of the second input register with the output of the third input register and a first adder for adding the output of the first input register to the output of the first multiplier. A first output register selects and stores one of the output of the first multiplier and the output of the first adder and outputs the selected one of the output of the first multiplier and the output of the first adder as the even-degree coefficient output, and provides input data to the first input register through the first bypass bus.
In one embodiment, the second data path includes a second register fetch unit which includes (i) a fourth input register for receiving, storing, and outputting the output of the odd-degree connection polynomial coefficient register block, (ii) a fifth input register for selecting, storing and outputting one of the output of the odd-degree correction polynomial coefficient register block, the output of the even-degree connection polynomial coefficient register block, and the output of the odd-degree connection polynomial coefficient register block, and (iii) a sixth input register for selecting, storing and outputting one of the output of the discrepancy register block, the output of the odd-degree syndrome register block, and the data of a second bypass bus. A second execute unit includes a second multiplier for multiplying the output of the fifth input register with the output of the sixth input register and a second adder for adding the output of the fourth input register to the output of the second multiplier. A second output register selects and stores one of the output of the second multiplier and the output of the second adder and outputs the selected one of the output of the second multiplier and the output of the second adder as the odd-degree coefficient output. The second output register provides input data to the sixth input register through the second bypass bus.
In one embodiment, the delta output unit includes a third adder for adding the output of the first adder to the output of the second adder and a third output register for storing and outputting the output of the third adder.
In one embodiment, the even-degree correction polynomial coefficient register block and the odd-degree correction polynomial coefficient register block each comprise a plurality of registers. The output of a lower-degree register is input to the right upper-degree register.
The discrepancy register block can include an accumulator for obtaining the discrepancy value for updating the connection polynomial so as to continuously generate syndromes equal to previously known syndromes. The discrepancy register block can also include a delta register block having a first multiplexer for selectively outputting the delta output and the output of the accumulator and a register for storing the output of the first multiplexer and outputting the output of the first multiplexer to the accumulator. The discrepancy register block can also include an inversion unit for inverting the output of the accumulator and a second multiplexer for selectively outputting the output of the delta register block and the output of the inversion unit.
A Galios field processing apparatus for use in a Bose Chaudhuri Hocquenghem/Reed-Solomon (BCH/RS) decoder performs a feedback shift register (FSR) synthesis algorithm of Massey-Berlekamp. The apparatus includes a first processor for receiving even-degree syndrome values transmitted by a syndrome generating block, odd-degree coefficients of a connection polynomial and a discrepancy value, performing first predetermined operations related to even terms of a delta and even-degree coefficients of both of a correction polynomial and the connection polynomial, and outputting even-degree coefficients of the connection polynomial and a summation of the even terms of the delta, a second processor for receiving odd-degree syndrome values transmitted by the syndrome generating block, even-degree coefficients of the connection polynomial and the discrepancy value, performing second predetermined operations related to odd terms of the delta and odd-degree coefficients of the polynomials, and outputting odd-degree coefficients of the connection polynomial and a summation of the odd terms of the delta, a delta output unit for receiving and adding the summation of the even terms of the delta and the summation of the odd terms of the delta and outputting an addition result as a delta output, a discrepancy register block for receiving the delta output and storing the discrepancy values for updating the connection polynomial so as to continuously generate syndromes equal to previously known syndromes, and an output unit for synthesizing the even-degree coefficients of the connection polynomial and the odd-degree coefficients of the connection polynomial and outputting the synthesis results as the coefficients of an error location polynomial, according to a control signal.